#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;

class MedianFinder
{
    //建好的堆是空堆，不能在下面直接访问堆顶元素
    priority_queue<int> heapleft;
    priority_queue<int, vector<int>, greater<>> heapright;
public:
    MedianFinder() = default;

    void addNum(int num)
    {
        int m = heapleft.size(), n = heapright.size();
        if(m==n)
        {
            if(heapleft.empty() || num <= heapleft.top())//必须判空在前，如果访问top在前，可能堆为空导致运行失败
            {
                heapleft.push(num);
            }
            else
            {
                heapright.push(num);
                heapleft.push(heapright.top());
                heapright.pop();
            }
        }
        else
        {
            if(num <= heapleft.top())
            {
                heapleft.push(num);
                heapright.push(heapleft.top());
                heapleft.pop();
            }
            else
            {
                heapright.push(num);
            }
        }
    }

    double findMedian()
    {
        if(heapleft.size() == heapright.size())
        {
            return (heapleft.top()+heapright.top())/2.0;
        }
        else
        {
            return heapleft.top();
        }
    }
};